{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Watering Plants"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wateringPlants"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给植物浇水"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你打算用一个水罐给花园里的 <code>n</code> 株植物浇水。植物排成一行，从左到右进行标记，编号从 <code>0</code> 到 <code>n - 1</code> 。其中，第 <code>i</code> 株植物的位置是 <code>x = i</code> 。<code>x = -1</code>&nbsp;处有一条河，你可以在那里重新灌满你的水罐。</p>\n",
    "\n",
    "<p>每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>按从左到右的顺序给植物浇水。</li>\n",
    "\t<li>在给当前植物浇完水之后，如果你没有足够的水 <strong>完全</strong> 浇灌下一株植物，那么你就需要返回河边重新装满水罐。</li>\n",
    "\t<li>你 <strong>不能</strong> 提前重新灌满水罐。</li>\n",
    "</ul>\n",
    "\n",
    "<p>最初，你在河边（也就是，<code>x = -1</code>），在 x 轴上每移动 <strong>一个单位</strong>&nbsp;都需要 <strong>一步</strong> 。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>plants</code> ，数组由 <code>n</code> 个整数组成。其中，<code>plants[i]</code> 为第 <code>i</code> 株植物需要的水量。另有一个整数 <code>capacity</code> 表示水罐的容量，返回浇灌所有植物需要的 <strong>步数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>plants = [2,2,3,3], capacity = 5\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：</strong>从河边开始，此时水罐是装满的：\n",
    "- 走到植物 0 (1 步) ，浇水。水罐中还有 3 单位的水。\n",
    "- 走到植物 1 (1 步) ，浇水。水罐中还有 1 单位的水。\n",
    "- 由于不能完全浇灌植物 2 ，回到河边取水 (2 步)。\n",
    "- 走到植物 2 (3 步) ，浇水。水罐中还有 2 单位的水。\n",
    "- 由于不能完全浇灌植物 3 ，回到河边取水 (3 步)。\n",
    "- 走到植物 3 (4 步) ，浇水。\n",
    "需要的步数是 = 1 + 1 + 2 + 3 + 3 + 4 = 14 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>plants = [1,1,1,4,2,3], capacity = 4\n",
    "<strong>输出：</strong>30\n",
    "<strong>解释：</strong>从河边开始，此时水罐是装满的：\n",
    "- 走到植物 0，1，2 (3 步) ，浇水。回到河边取水 (3 步)。\n",
    "- 走到植物 3 (4 步) ，浇水。回到河边取水 (4 步)。\n",
    "- 走到植物 4 (5 步) ，浇水。回到河边取水 (5 步)。\n",
    "- 走到植物 5 (6 步) ，浇水。\n",
    "需要的步数是 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>plants = [7,7,7,7,7,7,7], capacity = 8\n",
    "<strong>输出：</strong>49\n",
    "<strong>解释：</strong>每次浇水都需要重新灌满水罐。\n",
    "需要的步数是 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == plants.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= plants[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>max(plants[i]) &lt;= capacity &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [watering-plants](https://leetcode.cn/problems/watering-plants/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [watering-plants](https://leetcode.cn/problems/watering-plants/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,3,3]\\n5', '[1,1,1,4,2,3]\\n4', '[7,7,7,7,7,7,7]\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans = 0\n",
    "        total = capacity\n",
    "        for i, need in enumerate(plants):\n",
    "            if capacity >= need:\n",
    "                ans += 1\n",
    "                capacity -= need\n",
    "            else:\n",
    "                ans += 2 * i + 1\n",
    "                capacity = total - need\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants, capacity: int) -> int:\n",
    "        step = 0\n",
    "        temp = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if capacity>=plants[i]:\n",
    "                capacity -= plants[i]\n",
    "                step+=1\n",
    "            else:\n",
    "                capacity = temp\n",
    "                capacity-=plants[i]\n",
    "                step+=(i+1)*2-1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        n, ans, x, cur = len(plants), 0, -1, capacity\n",
    "        for i in range(n):\n",
    "            if cur >= plants[i]:\n",
    "                cur -= plants[i]\n",
    "                ans += i - x\n",
    "            else:\n",
    "                cur = capacity - plants[i]\n",
    "                ans += i + x + 2\n",
    "            x = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        steps = 0\n",
    "        n = len(plants)\n",
    "        v = capacity\n",
    "\n",
    "        for i in range(n):\n",
    "            if plants[i] <= capacity:\n",
    "                capacity -= plants[i]\n",
    "                steps += 1\n",
    "            else:\n",
    "                capacity = v\n",
    "                steps += i*2 + 1\n",
    "                capacity -= plants[i]\n",
    "\n",
    "        return steps \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        n = len(plants)\n",
    "        i = 0\n",
    "        tmp = 0\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            if tmp < plants[i]:\n",
    "                res += i * 2\n",
    "                tmp = capacity\n",
    "            else:\n",
    "                tmp -= plants[i]\n",
    "                res += 1\n",
    "                i += 1\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        steps = 0\n",
    "        current_capacity = capacity\n",
    "\n",
    "        for i, water_needed in enumerate(plants):\n",
    "        # 如果当前容量不够浇下一株植物，则返回河边装水\n",
    "            if water_needed > current_capacity:\n",
    "            # 返回河边并再次走到当前位置\n",
    "                steps += i * 2\n",
    "            # 重新装满水罐\n",
    "                current_capacity = capacity\n",
    "        \n",
    "        # 浇水，并移动到下一株植物\n",
    "            current_capacity -= water_needed\n",
    "            steps += 1\n",
    "\n",
    "        return steps\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        t=0\n",
    "        s=capacity\n",
    "        for i in range (0,len(plants)):\n",
    "            if s<plants[i]:\n",
    "                t=t+i+1+i\n",
    "                s=capacity\n",
    "                s=s-plants[i]\n",
    "            else:\n",
    "                t=t+1\n",
    "                s=s-plants[i]\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        n = len(plants)\n",
    "        i = 0\n",
    "        tmp = capacity\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            w = plants[i]\n",
    "            if tmp < w:\n",
    "                res += i * 2 + 1\n",
    "                tmp = capacity\n",
    "            else:\n",
    "                res += 1\n",
    "            tmp -= w\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        n = len(plants)\n",
    "        i = 0\n",
    "        tmp = capacity\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            w = plants[i]\n",
    "            if tmp < w:\n",
    "                res += i * 2 + 1\n",
    "                tmp = capacity\n",
    "                tmp -=w\n",
    "                i += 1\n",
    "            else:\n",
    "                tmp -= w\n",
    "                res += 1\n",
    "                i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans = 0\n",
    "        cntCap = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if cntCap >= plants[i]:\n",
    "                cntCap -= plants[i]\n",
    "                ans += 1\n",
    "            else:\n",
    "                ans += 2 * i + 1\n",
    "                cntCap = capacity - plants[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        water = capacity\n",
    "        n = len(plants)\n",
    "        plants.append(0)\n",
    "        while cur < n:\n",
    "            water -= plants[cur]\n",
    "            if water < plants[cur+1]:\n",
    "                ans += cur + 1 << 1\n",
    "                water = capacity\n",
    "            ans += 1\n",
    "            cur += 1\n",
    "            \n",
    "            \n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, ps: List[int], c: int) -> int:\n",
    "        init = c\n",
    "        res = 0\n",
    "        for i, p in enumerate(ps):\n",
    "            if init - p < 0:\n",
    "                res += i * 2\n",
    "                init = c\n",
    "            res += 1\n",
    "            init -= p\n",
    "            # print(i, init, res)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, rest = 0, capacity\n",
    "\n",
    "        for i, plant in enumerate(plants):\n",
    "            if rest >= plants[i]:\n",
    "                rest -= plants[i]\n",
    "            else:\n",
    "                ans += i * 2\n",
    "                rest = capacity - plants[i]\n",
    "        \n",
    "        return ans + len(plants)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans=0\n",
    "        \n",
    "        c=capacity\n",
    "        for i in range(len(plants)):\n",
    "            if c>=plants[i]:\n",
    "                c-=plants[i]\n",
    "                ans+=1\n",
    "            else:\n",
    "                c=capacity-plants[i]\n",
    "                ans+=i+i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, rest = 0, capacity\n",
    "\n",
    "        for i, plant in enumerate(plants):\n",
    "            if rest >= plants[i]:\n",
    "                ans += 1\n",
    "                rest -= plants[i]\n",
    "            else:\n",
    "                ans += i * 2 + 1\n",
    "                rest = capacity - plants[i]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        left = 0 \n",
    "        now = 0\n",
    "        ans = 0\n",
    "        while left < len(plants) : \n",
    "            while left < len(plants) and now + plants[left] <= capacity : \n",
    "                now += plants[left]\n",
    "                left += 1\n",
    "                ans += 1\n",
    "            if left < len(plants) and now + plants[left] > capacity :\n",
    "                ans += left * 2 \n",
    "                now = 0\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants, capacity: int) -> int:\n",
    "        step = 0\n",
    "        temp = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if capacity>=plants[i]:\n",
    "                capacity -= plants[i]\n",
    "                step+=1\n",
    "            else:\n",
    "                capacity = temp\n",
    "                capacity-=plants[i]\n",
    "                step+=(i+1)*2-1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        n = len(plants)\n",
    "        i = 0\n",
    "        tmp = capacity\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            w = plants[i]\n",
    "            if tmp < w:\n",
    "                res += i * 2\n",
    "                tmp = capacity\n",
    "            tmp -= w\n",
    "            res += 1\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        step = 0\n",
    "        now_capacity = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if now_capacity >= plants[i]:\n",
    "                step += 1\n",
    "                now_capacity -= plants[i]\n",
    "            else:\n",
    "                now_capacity = capacity - plants[i]\n",
    "                step += i*2 + 1\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans = 0\n",
    "        cntCap = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if cntCap >= plants[i]:\n",
    "                cntCap -= plants[i]\n",
    "                ans += 1\n",
    "            else:\n",
    "                ans += 2 * i + 1\n",
    "                cntCap = capacity\n",
    "                cntCap -= plants[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        cap = capacity\n",
    "        step, now = 0, 0\n",
    "        while now != len(plants):\n",
    "            if capacity >= plants[now]:\n",
    "                capacity -= plants[now]\n",
    "                step += 1\n",
    "                now += 1\n",
    "            else:\n",
    "                capacity = cap\n",
    "                step += now * 2\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, n = 0, len(plants)\n",
    "        tmp = capacity\n",
    "        for i in range(n):\n",
    "            if plants[i] <= tmp:\n",
    "                ans += 1\n",
    "                tmp -= plants[i]\n",
    "            else:\n",
    "                tmp = capacity - plants[i]\n",
    "                ans += i + i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, rest = 0, capacity\n",
    "\n",
    "        for i, plant in enumerate(plants):\n",
    "            if rest >= plants[i]:\n",
    "                ans += 1\n",
    "                rest -= plants[i]\n",
    "            else:\n",
    "                ans += i * 2 + 1\n",
    "                rest = capacity - plants[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, rest = 0, capacity\n",
    "\n",
    "        for i, plant in enumerate(plants):\n",
    "            if rest >= plant:\n",
    "                rest -= plant\n",
    "            else:\n",
    "                ans += i << 1\n",
    "                rest = capacity - plant\n",
    "        \n",
    "        return ans + len(plants)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, water = 0, capacity\n",
    "        for i, x in enumerate(plants):\n",
    "            if water < x:\n",
    "                ans += 2 * i\n",
    "                water = capacity\n",
    "            water -= x\n",
    "        return ans + len(plants)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        cur_capa = 0\n",
    "        res = 0\n",
    "        for i, p in enumerate(plants):\n",
    "            if p + cur_capa <= capacity: \n",
    "                res += 1\n",
    "                cur_capa += p\n",
    "            else:\n",
    "                res +=  2 * i\n",
    "                res += 1\n",
    "                cur_capa = p\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        step = 0\n",
    "        water = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if water >= plants[i]:\n",
    "                step += 1\n",
    "                water -= plants[i]\n",
    "            else:\n",
    "                step += 2 * i + 1\n",
    "                water = capacity -plants[i]\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, rest = len(plants), capacity\n",
    "\n",
    "        for i, plant in enumerate(plants):\n",
    "            if rest < plant:\n",
    "                ans += i << 1\n",
    "                rest = capacity\n",
    "            rest -= plant\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        x = -1\n",
    "        n = len(plants)\n",
    "        c = capacity\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if c < plants[i]:\n",
    "                ret += (x + 1) * 2 + 1\n",
    "                c = capacity\n",
    "            else:\n",
    "                ret += 1\n",
    "            c -= plants[i] \n",
    "            x = i\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans = len(plants) \n",
    "        c = capacity\n",
    "        for i, x in enumerate(plants, 1):\n",
    "            if c >= x:\n",
    "                c -= x\n",
    "            else:\n",
    "                ans += (i - 1) * 2\n",
    "                c = capacity - x\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        step,i,n,full = 0,0,len(plants),capacity\n",
    "        while i<n:\n",
    "            if capacity>=plants[i]:\n",
    "                step += 1\n",
    "                capacity-=plants[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                step += 2*i\n",
    "                capacity = full \n",
    "        return step\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans , s = 0, capacity\n",
    "        for i, x in enumerate(plants):\n",
    "            if x <= s:\n",
    "                ans += 1\n",
    "                s -= x\n",
    "            else:\n",
    "                s = capacity - x\n",
    "                ans += i * 2 + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, rest = 0, capacity\n",
    "\n",
    "        for i, plant in enumerate(plants):\n",
    "            if rest >= plant:\n",
    "                ans += 1\n",
    "                rest -= plant\n",
    "            else:\n",
    "                ans += (i*2+1)\n",
    "                rest = capacity - plant\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        需要步数 = 0\n",
    "        水量 = capacity\n",
    "        for i, j in enumerate(plants):\n",
    "            if 水量 >= j:\n",
    "                需要步数 += 1\n",
    "            else:\n",
    "                需要步数 += i*2+1\n",
    "                水量 = capacity\n",
    "            水量 -= j\n",
    "        return 需要步数\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants, capacity: int) -> int:\n",
    "        step = 0\n",
    "        temp = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if capacity>=plants[i]:\n",
    "                capacity -= plants[i]\n",
    "                step+=1\n",
    "            else:\n",
    "                capacity = temp\n",
    "                capacity-=plants[i]\n",
    "                step+=(i+1)*2-1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        count = 0\n",
    "        has = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if has >= plants[i]:\n",
    "                count = count + 1\n",
    "                has = has - plants[i]\n",
    "            else:\n",
    "                has = capacity - plants[i]\n",
    "                count += i * 2 + 1\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        step,i,n,full = 0,0,len(plants),capacity\n",
    "        while i<n:\n",
    "            if capacity>=plants[i]:\n",
    "                step += 1\n",
    "                capacity-=plants[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                step += 2*i\n",
    "                capacity = full \n",
    "        return step\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        n = len(plants)\n",
    "        i = 0\n",
    "        tmp = capacity\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            w = plants[i]\n",
    "            if tmp < w:\n",
    "                res += i * 2\n",
    "                tmp = capacity\n",
    "            tmp -= w\n",
    "            res += 1\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        n = len(plants)\n",
    "        i = 0\n",
    "        tmp = capacity\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            w = plants[i]\n",
    "            if tmp < w:\n",
    "                res += i * 2\n",
    "                tmp = capacity\n",
    "            else:\n",
    "                tmp -= w\n",
    "                res += 1\n",
    "                i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants, capacity: int) -> int:\n",
    "        step = 0\n",
    "        temp = capacity\n",
    "        for i in range(len(plants)):\n",
    "            if capacity>=plants[i]:\n",
    "                capacity -= plants[i]\n",
    "                step+=1\n",
    "            else:\n",
    "                capacity = temp\n",
    "                capacity-=plants[i]\n",
    "                step+=(i+1)*2-1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans, cap = 0, capacity \n",
    "        for i, p in enumerate(plants):\n",
    "            if cap >= p:\n",
    "                cap -= p\n",
    "                ans += 1\n",
    "            else:\n",
    "                ans += (i << 1) + 1\n",
    "                cap = capacity - p\n",
    "        return ans            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        ans=0\n",
    "        rest=capacity\n",
    "\n",
    "        for i,_ in enumerate(plants):\n",
    "            if rest>=plants[i]:\n",
    "                ans+=1\n",
    "                rest-=plants[i]\n",
    "            else:\n",
    "                ans+=i*2+1\n",
    "                rest=capacity-plants[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        step = -1 # 人物所在位置\n",
    "        total_walk = 0\n",
    "        initial_capacity = capacity # 保存水壶容量\n",
    "        for index,value in enumerate(plants):\n",
    "            # 水量足够\n",
    "            if capacity >= value:\n",
    "                # 浇水\n",
    "                capacity -= value\n",
    "                # 更新人物位置\n",
    "                step = index \n",
    "                total_walk += 1\n",
    "            else:\n",
    "                # 水量不足时(人物需到小河边取水)(一个来回)\n",
    "                ## 人物位置不变，但总步数会增加\n",
    "                total_walk += 2*(step + 1)\n",
    "                ## 蓄水\n",
    "                capacity = initial_capacity\n",
    "                ## 浇灌\n",
    "                capacity -= value\n",
    "                step = index\n",
    "                total_walk += 1\n",
    "        return total_walk\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        left = 0 \n",
    "        now = 0\n",
    "        ans = 1\n",
    "        while left <= len(plants) - 1 : \n",
    "            while left < len(plants) and now + plants[left] <= capacity : \n",
    "                now += plants[left]\n",
    "                left += 1\n",
    "                ans += 1\n",
    "            if left < len(plants) and now + plants[left] > capacity :\n",
    "                ans += left * 2 \n",
    "                now = 0\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        cur = capacity\n",
    "\n",
    "        for i, p in enumerate(plants):\n",
    "            res += 1\n",
    "            if cur < p:\n",
    "                res += 2 *  i \n",
    "                cur = capacity\n",
    "            \n",
    "            cur = cur - p\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        cur = capacity;n = len(plants)\n",
    "        res = 0\n",
    "        for idx,i in enumerate(plants):\n",
    "            cur -= i\n",
    "            res += 1\n",
    "            if idx == n-1:continue\n",
    "            if cur < plants[idx+1]:\n",
    "                res+=idx*2+2;cur = capacity\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wateringPlants(self, plants: List[int], capacity: int) -> int:\n",
    "        res=0\n",
    "        l=len(plants)\n",
    "        i=0\n",
    "        temp=capacity\n",
    "        while i<l:\n",
    "            if capacity>=plants[i]:\n",
    "                res+=1\n",
    "                capacity-=plants[i]\n",
    "                i=i+1\n",
    "            else:\n",
    "                res+=i\n",
    "                capacity=temp\n",
    "                res+=i \n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
